package org.nowcoder.leetcode.twoPointers;

/**
 * Title  : 876. Middle of the Linked List
 * Source : https://leetcode.cn/problems/middle-of-the-linked-list/
 * Author : XrazYang
 * Date   : 2023-10-21
 */

public class LeetCode_876 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 常规解法：
     * 1. 扁平化
     * 2. 两次遍历
     */
    public ListNode middleNode(ListNode head) {
        //快慢指针
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}
